package leetcode.editor.cn;
//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 
//
// 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "1 + 1"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：s = " 2-1 + 2 "
//输出：3
// 
//
// 示例 3： 
//
// 
//输入：s = "(1+(4+5+2)-3)+(6+8)"
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 3 * 105 
// s 由数字、'+'、'-'、'('、')'、和 ' ' 组成 
// s 表示一个有效的表达式 
// '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效) 
// '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的) 
// 输入中不存在两个连续的操作符 
// 每个数字和运行的计算将适合于一个有符号的 32位 整数 
// 
// Related Topics 栈 递归 数学 字符串 
// 👍 893 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution76 {
    public int calculate(String s) {
        Deque<Character> characters = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c != ' ') {
                characters.add(c);
            }
        }
        return helper(characters);
    }

    /**
     * 采用后缀表达式
     * @param s
     * @return
     */
    public int calculate1(String s) {
        return 0;
    }

    /**
     * 1、先给第一个数字加一个默认符号 +，变成 +1-12+3。
     * <p>
     * 2、把一个运算符和数字组合成一对儿，也就是三对儿 +1，-12，+3，把它们转化成数字，然后放到一个栈中。
     * <p>
     * 3、将栈中所有的数字求和，就是原算式的结果。
     * <p>
     * 其实思路跟仅处理加减法没啥区别，拿字符串 2-3*4+5 举例，核心思路依然是把字符串分解成符号和数字的组合。
     * <p>
     * 比如上述例子就可以分解为 +2，-3，*4，+5 几对儿，我们刚才不是没有处理乘除号吗，很简单，其他部分都不用变，
     *
     * @param s
     * @return
     */
    private int helper(Deque<Character> s) {
        // 计算栈
        Deque<Integer> stack = new LinkedList<>();
        char sign = '+';
        int num = 0;
        while (!s.isEmpty()) {
            Character c = s.pop();
            if (Character.isDigit(c)) {
                num = 10 * num + Character.getNumericValue(c);
            }

            // 遇到左括号开始递归计算 num
            if (c == '(') {
                num = helper(s);
            }

            if (!Character.isDigit(c) || s.isEmpty()) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    Integer last = stack.pop();
                    stack.push(last * num);
                } else if (sign == '/') {
                    Integer last = stack.pop();
                    stack.push(last / num);
                }
                sign = c;
                num = 0;
            }
            if (sign == ')') {
                break;
            }
        }
        int sum = 0;
        for (int i : stack) {
            sum += i;
        }
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
